package algorithm;

public class leetcode_0132 {
    public int minCut(String s) {
        int len=s.length();
        int [] dp=new int[len];
        for(int i=0;i<len;++i){
            dp[i]=len;
        }
        dp[0]=0;
        for(int i=1;i<len;++i){
            if(ishuiwen(s,0,i)){
                dp[i]=0;
            }
            else{
                for(int j=1;j<=i;++j){
                    if(ishuiwen(s,j,i)){
                        dp[i]=Math.min(dp[i],dp[j-1]+1);
                    }
                }
            }
        }
        return dp[len-1];
    }
    public boolean ishuiwen(String s,int left,int right){
        while(left<right){
            if(s.charAt(left)!=s.charAt(right)) return false;
            left++;right--;
        }
        return true;
    }
}
